def find_cycles(arr):
'''
[where 1 goes, where 2 goes, ... where n goes]
'''
n = len(arr)
round = 0
first_visited = [0 for i in range(n)]
cycles = []
for i in range(n):
if first_visited[i] == 0:
round += 1
index = i
while first_visited[index] == 0:
first_visited[index] = round
index = arr[index]
if first_visited[index] == round:
cycle = [index]
next = arr[index]
while next != index:
cycle.append(next)
next = arr[next]
cycles.append(cycle)
return cycles
for _ in range(int(input())):
n, k = map(int, input().split())
b = list(map(lambda x: int(x)-1, input().split()))
if k == 1:
if all(b[i]==i for i in range(n)):
print('YES')
else:
print('NO')
else:
for c in find_cycles(b):
if len(c) != k:
print('NO')
break
else:
print('YES')#include <bits/stdc++.h>
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define all(x) (x).begin(), (x).end()
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order, order_of_key
void solve() {
ll n, k;
cin >> n >> k;
vector<ll> v(n);
for (auto &i : v) {
cin >> i;
i--;
}
// idea : cycle size should be k
vector<ll> next(n);
for (ll i = 0; i < n; i++) {
next[i] = v[i];
}
vector<ll> vis(n, 0), cycle(n, 0);
function<ll(ll)> calc = [&] (ll a) {
if (vis[a] == 1) {
if (cycle[a] != 0) return cycle[a];
ll sz = 1;
ll k = a;
while (next[k] != a) {
sz++;
k = next[k];
}
return cycle[a] = sz;
}
vis[a] = 1;
return cycle[a] = calc(next[a]);
};
for (ll i = 0; i < n; i++) {
if (vis[i] == 0) {
cycle[i] = calc(i);
}
}
for (ll i = 0; i < n; i++) {
if (k != 1 && cycle[i] != k) {
cout << "No\n";
return;
}
if (v[i] != i && k == 1) {
cout << "No\n";
return;
}
}
cout << "Yes\n";
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}17. Letter Combinations of a Phone Number | 5. Longest Palindromic Substring |
3. Longest Substring Without Repeating Characters | 1312. Minimum Insertion Steps to Make a String Palindrome |
1092. Shortest Common Supersequence | 1044. Longest Duplicate Substring |
1032. Stream of Characters | 987. Vertical Order Traversal of a Binary Tree |
952. Largest Component Size by Common Factor | 212. Word Search II |
174. Dungeon Game | 127. Word Ladder |
123. Best Time to Buy and Sell Stock III | 85. Maximal Rectangle |
84. Largest Rectangle in Histogram | 60. Permutation Sequence |
42. Trapping Rain Water | 32. Longest Valid Parentheses |
Cutting a material | Bubble Sort |
Number of triangles | AND path in a binary tree |
Factorial equations | Removal of vertices |
Happy segments | Cyclic shifts |
Zoos | Build a graph |
Almost correct bracket sequence | Count of integers |